let Point = require('./models/Point')

const MAX_LNG = 136;
const MIN_LNG = 73;
const MAX_LAT = 54;
const MIN_LAT = 0;
const MAX_LEVEL = 18;

const POW2 = {} // 缓存2的n次方，后面会多次使用
const UNIT_LNG = {} // {节点级别:单位经度}
const UNIT_LAT = {} // {节点级别:单位纬度}
for (let i = 0; i <= MAX_LEVEL; i++) {
    POW2[i] = Math.pow(2, i);
    UNIT_LNG[i] = (MAX_LNG - MIN_LNG) / POW2[i];
    UNIT_LAT[i] = (MAX_LAT - MIN_LAT) / POW2[i];
}

/**
 * 四叉树索引
 */
class QuadTreeNode {
    /**
     * 构造函数
     * @param level 当前节点的层级，默认0级=根节点
     */
    constructor(level) {
        this.level = level ? level : 0
        if (this.level === MAX_LEVEL) {
            this.points = [] //存储数据
        } else {
            this.children = [null, null, null, null] //子节点
        }
    }

    /**
     * 插入点
     * @param point Point 点对象
     */
    insert(point) {
        if (this.level === MAX_LEVEL) {
            // 如果是叶子结点，直接存储数据
            this.points.push(point)
        } else {
            // 不是叶子结点，判断属于哪个子节点
            let childLevel = this.level + 1
            let x = Math.floor((point.lng - MIN_LNG) / UNIT_LNG[childLevel]) % 2
            let y = Math.floor((point.lat - MIN_LAT) / UNIT_LAT[childLevel]) % 2
            let index = x + 2 * y
            // 子节点不存在就创建一个
            if (this.children[index] === null) {
                this.children[index] = new QuadTreeNode(childLevel)
            }
            // 递归调用子节点的insert方法
            this.children[index].insert(point)
        }
    }

    /**
     * 查询最近的点
     * @param origin Point 原点
     * @param number int 查询附近点的数量
     * @returns Array 附近点数组
     */
    findNearestPoint(origin, number) {
        return this._findNearestPoint(origin, 1, number)
    }

    /**
     * 使用最高经度的节点，一圈一圈往外查，直到找到最近的一个点
     * @param origin Point 原点
     * @param scope 查询范围，从1开始，每次增加1
     * @param number 查询的数量
     * @returns [] 附近点数组
     */
    _findNearestPoint(origin, scope, number) {
        if (scope >= 500) {
            throw new Error('查询附近的点失败')
        }
        let nodeList = []
        if (scope === 1) {
            let originNode = this._findNode(origin, MAX_LEVEL)
            if (originNode !== null) {
                nodeList.push(originNode)
            }
        }

        for (let x = -scope; x <= scope; x++) {
            for (let y = -scope; y <= scope; y++) {
                if (Math.abs(x) !== scope && Math.abs(y) !== scope) {
                    continue; // 只查外圈，中间已经查过了
                }
                let p = new Point(origin.lng + UNIT_LNG[MAX_LEVEL] * x, origin.lat + UNIT_LAT[MAX_LEVEL] * y)
                let node = this._findNode(p, MAX_LEVEL)
                if (node !== null) {
                    nodeList.push(node)
                }
            }
        }

        let points = [];
        for (let node of nodeList) {
            points.push(...node._getPoints())
        }

        if (number <= 0) {
            // 上一层已经凑够点的数量，但多找一圈，免得漏掉一些更近的点
            return points
        } else {
            // 范围内没有足够的点，扩大一圈继续递归
            let pointList = this._findNearestPoint(origin, scope + 1, number - points.length)
            points.push(...pointList)
        }

        // 外层直接返回结果
        if (scope !== 1) {
            return points
        }
        // 跳出递归到最里层的时候，拿到所有遍历的点，进行排序
        let list = points.map(p => {
            return {
                point: p,
                distance: origin.distance(p)
            }
        })
        // 升序排列
        list.sort((a, b) => a.distance - b.distance)
        // 取距离最短的number个点
        return list.slice(0, number).map(item => item.point)
    }

    /**
     * 根据点(经纬度)查询对应级别的节点
     * @param point Point 点
     * @param level int 四叉树层级
     * @returns {QuadTreeNode|null} 节点或Null
     */
    _findNode(point, level) {
        if (level === undefined || level < 0 || level > MAX_LEVEL) {
            throw new Error('findNode:level参数必须为0-' + MAX_LEVEL.toString())
        }
        if (this.level > level) {
            throw new Error('findNode:level参数必须大于当前节点level')
        }
        // 找到节点，返回节点对象
        if (level === this.level) {
            return this
        }
        // 计算子节点
        let childLevel = this.level + 1
        let x = Math.floor((point.lng - MIN_LNG) / UNIT_LNG[childLevel]) % 2
        let y = Math.floor((point.lat - MIN_LAT) / UNIT_LAT[childLevel]) % 2
        let index = x + 2 * y
        return this.children[index] ? this.children[index]._findNode(point, level) : null
    }

    /**
     * 获取当前节点下的所有点
     * @returns [] 点数组
     */
    _getPoints() {
        if (this.level === MAX_LEVEL) {
            // 如果是叶子结点，就返回数据数组的副本
            return this.points.slice(0)
        }
        let points = [];
        // 递归子节点
        for (let i = 0; i < 4; i++) {
            if (this.children[i]) {
                let childPoints = this.children[i]._getPoints()
                points.push(...childPoints) // 数组合并
            }
        }
        return points;
    }


}

module.exports = QuadTreeNode;